package algorithm

import (
	"code.byted.org/mobaijie/parallel_bfs/data_structure"
	"code.byted.org/mobaijie/parallel_bfs/lock"
	"sync"
)

type ParallelBFSHandler struct {
	adjacencyList [][]int32
	ifVisit       []bool
	objLock       *lock.ObjLock
}

const (
	GrainSize = 1024
)

func NewParallelBFSHandler(graphFilePath string) {
	lock.InitObjLock()
}

func (p *ParallelBFSHandler) ParallelBFS() {

}

// 处理单个槽位中的Pennant
func (p *ParallelBFSHandler) processPennant(inPennant *data_structure.Pennant, outBag *data_structure.Bag, inSize int) {
	if inSize <= GrainSize {
		// 若当前pennant的规模不大于指定单协程处理规模，那么就在这里串行处理
		// 由于要遍历pennant(一棵树)中的所有节点，一种方式是深度优先搜索，但
		// 因为递归效率较低，这里采用广度优先搜索。此处使用串行版的广度优先搜索。
		queue := data_structure.NewBlockingQueue()
		size := int32(1)
		queue.Offer(&inPennant)
		for !queue.IsEmpty() {
			size = queue.Len()
			for i := int32(0); i < size; i++ {
				head := queue.Pull()
				pennantHead, _ := head.(*data_structure.Pennant)
				p.handleOneTreeNode(pennantHead, outBag)
				if pennantHead.Left != nil {
					queue.Offer(pennantHead.Left)
				}
				if pennantHead.Right != nil {
					queue.Offer(pennantHead.Right)
				}
			}
		}
	}
	var wg sync.WaitGroup
	wg.Add(1)
	newPennant := inPennant.Split()
	// 将处理规模二分处理，分给子协程处理
	go func() {
		p.processPennant(newPennant, outBag, inSize/2)
		wg.Done()
	}()
	// 当前协程一半数据
	p.processPennant(inPennant, outBag, inSize/2)
	wg.Wait()
}

// 处理Pennant中单个树节点
func (p *ParallelBFSHandler) handleOneTreeNode(pennant *data_structure.Pennant, outBag *data_structure.Bag) {
	// 当前图节点的所有子节点
	list := p.adjacencyList[pennant.Val]
	for _, son := range list {
		// 如果子节点没有被遍历过，而且抢锁(对象锁，就是相当于Java中的synchronized(obj))
		if !p.ifVisit[son] && p.objLock.TryLock(&son) {
			p.ifVisit[son] = true
			outBag.InsertWithHopper(son)
		}
	}
}
